class MergeSort():
    def __init__(self) -> None:
        self.count = 0

    def merge(self,L,R):
        i,j = 0,0
        res = []
        while i<len(L) and j<len(R):
            self.count+=1
            if L[i]<R[j]:
                res.append(L[i])
                i+=1
            else:
                res.append(R[j])
                j+=1
        # 左半区剩下的元素
        while i<len(L):
            res.append(L[i])
            i+=1
        # 右半区剩下的元素
        while j<len(R):
            res.append(R[j])
            j+=1    
        # res为组合了L，R的有序列表
        return res

    def sort(self,ls):
        length = len(ls)
        if length<=1:
            return ls
        else:
            mid = length//2
            left = self.sort(ls[:mid])
            right = self.sort(ls[mid:])
            return self.merge(left,right)

    # 判断是否有序
    def isSorted(self,ls):
        for i in range(1,len(ls)):
            if ls[i]<ls[i-1]:
                return False
        return True